package com.leetcode.offer;

import com.leetcode.entity.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zfl
 * @Classname GetIntersectionNode
 * @Description 两个链表的第一个公共节点
 * @Date 2020/11/26 16:06
 */
public class GetIntersectionNode {

    /**
     * @param headA
     * @param headB
     * @return
     * 此解法适合链表有环的解法，当链表没有环时，可以采用双指针法
     * 执行用时：10 ms, 在所有 Java 提交中击败了8.46%的用户
     * 内存消耗：42.4 MB, 在所有 Java 提交中击败了5.02%的用户
     */
    public static ListNode getIntersectionNode(ListNode headA,ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode p = headA;
        while (!set.contains(p) && p != null) {
            set.add(p);
            p = p.next;
        }
        p = headB;
        while (p != null) {
            if (set.contains(p)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    /**
     * @param headA
     * @param headB
     * @return
     * 双指针法
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了70.88%的用户
     */
    public static ListNode getIntersectionNode2(ListNode headA,ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA, p2 = headB;
        int count = 0;
        while (p1 != p2 && count < 2) {

            if(p1.next == null) {
                p1 = headB;
                count++;
            }else {
                p1 = p1.next;
            }

            if(p2.next == null) {
                p2 = headA;
            }else {
                p2 = p2.next;
            }
        }
        return count < 2 ? p1 : null;
    }
}
